Testing hardware, firmware, and software implementations of communications software, VLSI circuits, and rule based expert systems for conformance with specifications is critical in today's drive for total quality assurance. For example, release of a faulty VLSI circuit can cost a company millions of dollars. Similarly, release of faulty software can have life threatening implications.
The complexity of modern hardware, software, and firmware has grown to the point that exhaustive testing, that is testing every testable aspect of a product is impractical, or even infeasible. One reason for this is that a linear growth in the number of components results in exponential grown in the number of component interactions.
It is often helpful to test hardware, firmware, and software for conformance to their specifications. It would be often helpful to supply stimuli to a machine to be tested, then look inside the machine to see what happened, or indeed see how whatever happened did happen. However, it is often infeasible or impractical in many test situations to actually look into a circuit or software program to determine what its current status or state it is in. Rather, practicality requires that these machines be treated as black boxes--where all that a tester has available at any time are the output responses from the machine received in response to stimuli presented to the machine by the tester.
One approach to black box testing is disclosed in U.S. Pat. No. 4,692,921 to Anton T. Dahbura, et al. A number of Unique Input/Output (UIO) subsequences are developed. Input/Output test subsequences are constructed for Finite State Machine (FSM) edges to be tested by concatenating a head and a tail sequence to each edge to be tested. The head subsequence is a low cost I/O sequence designed to drive the machine under test from a known (reset) state to the state immediately preceding the state transition edge to be tested. The tail subsequence utilized is the UIO sequence constructed for the state immediately following the state transition to be tested.
The approach disclosed in the '921 patent application was extended in U.S. Pat. No. 4,991,176 to Anton T. Dahbura, et al. Instead of finding the shortest test subsequences, the I/O subsequence selection criteria was changed to minimize cost, where cost may be different than the number of I/O subsequences utilized. Secondly, the concepts of forming a graph with the generated test subsequences and touring the graph in order to generate a verification test sequence are disclosed.
The approach was similarly disclosed in a paper authored and edited in part by the '176 authors in an article titled "An Optimization Technique for Protocol Conformance Test Generation Based on UIO Sequences and Rural Postman Tours" in "Protocol Specification, Testing, and Verification, VIII", which were the proceedings of the IFIP WG 6.1 Eighth International Symposium on Protocol Specification, Testing, and Verification, held in Atlantic City, N.J., U.S.A. on Jun. 7-10, 1988. The use of a Chinese Postman tour to tour a subsequence graph was shown as a method of generating a verification test sequence.
An implementation of the Dahbura method discussed above was disclosed in an article titled "An Optimal Test Sequence for the JTAG/IEEE P1149.1 Test Access Port Controller" by Dahbura et al. which was presented at the IEEE 1989 International Test Conference. Test verification sequences were generated for the JTAG/IEEE P1149.1 architecture and applied. Test coverage was then evaluated.
The UIO sequences disclosed by Dahbura et al. extend from a transition edge-under-test forward. One of the applicants herein, Xiao Sun, in his Ph.D. dissertation titled "Automatic Conformance Testing of Protocols Implemented in Software or Hardware" from Texas A&M University, dated August 1993, introduced Backward Unique Input/Output (BUIO) sequences. These BUIO sequences are similar to Dahbura's UIO (hereinafter "FUIO") sequences, but differ in that the BUIO sequences precede an edge-under-test in a test subsequence. The use of BUIO sequences offers a number of advantages, including the ability to validate that a machine under test has been driven to a particular state. Additionally, Dr. Sun disclosed augmenting a test subsequence graph to make it symmetric, and the use of an Euler Tour to tour an augmented test subsequence graph.
The introduction and usage of BUIO sequences and augmentation of a test subsequence graph for conformance testing were further discussed in two papers co-authored by co-applicant Sun titled "Protocol Conformance Testing by Discriminating UIO Sequences", in "Protocol Specification, Testing, and Verification VI", sponsored by IFIP in 1991, and "On the Verification and Validation of Protocols with High Fault Coverage Using UIO Sequences", IEEE 1992.